package com.xxwy.lintcodes;

import com.xxwy.Error;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xxwy
 * 带重复元素的子集
 * 如果 S = [1,2,2]，一个可能的答案为：
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
 */
@Error
public class Num18 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // write your code here
        List<List<Integer>> results = new ArrayList<>();
        if(nums == null || nums.length ==0){
            return results;
        }
        Arrays.sort(nums);

        ArrayList<Integer> subset = new ArrayList<>();
        subsetsHelper(nums,0,subset,results);
        return results;
    }

    /**
     * 回溯
     * @param nums
     * @param startIndex
     * @param subset
     * @param results
     */
    private void subsetsHelper(int[] nums, int startIndex, ArrayList<Integer> subset, List<List<Integer>> results) {

        //deep copy subset & add to results
        results.add(new ArrayList<>(subset));
        for (int i = startIndex; i < nums.length; i++) {
            subset.add(nums[i]);
            subsetsHelper(nums,i+1,subset,results);
            subset.remove(subset.size()-1);
        }
    }
}
